//1.二分-搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(nums[l] < target) return nums.size();
        return l; 
    }
};


//2.二分-x的平方根
//解法一: 暴力枚举
class Solution {
public:
    int mySqrt(int x) {
        for(long long i = 0; i <= x; i++)
        {
            if(i * i == x) return i;
            if(i * i > x) return i - 1;
        }
        return -1;
    }
};

//解法二: 二分查找
class Solution {
public:
    int mySqrt(int x) {
        long long l = 0, r = x;
        while(l < r)
        {
            long long mid = l + (r - l + 1) / 2;
            if(mid * mid <= x) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};